package com.clstu.leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;

/**
 * 研究kmp算法
 */
public class KMP {

    public static void main(String[] args) {
        //LinkedList可以当做双端队列使用
        String s1 = "helllololololololoxx";
        String s2 = "x";
        System.out.println(s1.length());
        System.out.println(indexOf(s1,s2));
    }


    //编写一个方法,返回str2 在 str1的什么位置
    public static int indexOf(String str1,String str2){
        //如果长度都不匹配,直接找不到
        if(str2.length()>str1.length()) return -1;
        char[] chars1 = str1.toCharArray();
        char[] chars2 = str2.toCharArray();
        //根据返回的数组来加速字符串匹配
        int[] arr = getMaxPreLastEqualArr(str2);
        int i=0;
        while (true){
            //如果比较完
            if(i > str1.length()-str2.length()) break;
            //挨着比较
            //只用一个变量就可以了
            int x=0;
            while (true){
                //如果比较完
                if( x>=str2.length() || i+x >= str1.length()) break;
                //比较
                if(chars1[i+x] == chars2[x]){
                    x++;
                }else if(x == 0){
                    //如果再也不能向前跳了
                    i++;
                }else {
                    //向前跳(向前推)
                    //直接就到了最长前后缀相等的下一个位置
                    i = i+(x-arr[x]);
                    x = arr[x];
                }
            }
            //判断是否找到
            if(x == str2.length()) return i;
        }
        //没找到
        return -1;
    }

    //编写方法得到每个字符的最长前后缀序相等列
    public static int[] getMaxPreLastEqualArr(String str){
        //先判断是否长度为1
        if(str.length() == 1) return new int[]{-1};
        char[] chars = str.toCharArray();
        int[] arr = new int[str.length()];
        //准备好第一项和第二项
        arr[0] = -1;
        arr[1] = 0;
        //可以适当的利用前面的信息更快的得到这个数组
        int cn = 0;
        for(int i = 2;i<arr.length;i++){
            cn = arr[i-1];
            //根据前面的结果加速自己位置的判断
            while (true) {
                //如果当前字符等于前面一个最长前缀的下一个(cn位置),直接+1(注意不能包含全部)
                if (chars[i-1] == chars[cn] && cn<i-1) {
                    arr[i] = ++cn;
                    break;
                }else if(cn == 0){
                    //跳不了退出.用数组默认的0
                    break;
                }else {
                    //向前跳,
                    cn = arr[cn];
                }
            }
        }
        return arr;
    }
}
